package LeetCode.exercise;

import java.util.Stack;

public class LC946 {
    public static void main(String[] args) {
        LC946 l = new LC946();
        int[] pushed = new int[]{1,2,3,4,5};
        int[] popped = new int[]{4,5,3,2,1};
        System.out.println(l.validateStackSequences(pushed, popped));

    }
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int m = pushed.length;
        for(int i = 0, j = 0; i < pushed.length; i++){
            while(i < m && j < m && pushed[i] != popped[j]){
                stack.push(pushed[i++]);
            }
            j++;
            while(!stack.isEmpty() && popped[j] == stack.peek()){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}
